package fun.coding.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class SubsetsII {

	public static void main(String[] args) {

	}

	public List<List<Integer>> subsetsWithDup(int[] num) {
		List<List<Integer>> ans = new LinkedList<List<Integer>>();
		// Here I just simply used a set to remove dup, use extra space though
		Set<List<Integer>> finalRes = new HashSet<List<Integer>>();
		
		if (num == null || num.length == 0) return ans;
		Arrays.sort(num);
		
		List<Integer> res = new LinkedList<Integer>();
		helper(num, 0, finalRes, res);
		
		ans.addAll(finalRes);
		
		return ans;
    }
	
	private void helper(int[] s, int start, Set<List<Integer>> finalRes, List<Integer> res) {
		// every recursion step is a solution
		finalRes.add(new LinkedList<Integer>(res));
		
		for (int i = start; i < s.length; i++) {
			// another way to do this without extra space, I don't need a set, only single number can be dups
			// if (i != start && s[i] == s[i-1]) continue;
			
			res.add(s[i]);
			helper(s, i + 1, finalRes, res);
			res.remove(res.size() - 1);
		}
	}
}
